package org.example.likou150.land;


import java.util.ArrayList;
import java.util.List;

public class Solve {

    public static void main(String[] args) {

//        char[][] board = new char[][]{{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};

        char[][] board = new char[][]{{'O','X','X','O','X'},
                                      {'X','O','O','X','O'},
                                      {'X','O','X','O','X'},
                                      {'O','X','O','O','O'},
                                      {'X','X','O','X','O'}};


        Solve solve = new Solve();
        solve.solve(board);
        for (char[] chars : board) {
            for (char aChar : chars) {
                System.out.print(aChar);
            }
            System.out.println("");
        }
    }

    /**
    * 思路2：从边缘开始找，将连通的'O'设置成临时值，最终被包围的‘O’就变成‘X’,临时值恢复成‘O’
    * */
    public void solve(char[][] board) {
        for(int i=0; i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                if((i==0 || i==board.length-1 || j==0 || j==board[i].length-1) && board[i][j]=='O'){
                    dfs(board, i, j);
                }
            }
        }

        for(int i=0; i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else if(board[i][j] == '#'){
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(char[][] board, int i, int j){
        if(i<0 || i>=board.length || j<0 || j>=board[i].length){
            return;
        }

        if(board[i][j]=='X' || board[i][j]=='#'){
            return;
        }

        board[i][j]='#';
        dfs(board, i-1, j);
        dfs(board, i+1, j);
        dfs(board, i, j-1);
        dfs(board, i, j+1);
    }


    /*
    * 思路1： 找到所有“内陆”递归找到符合条件的进行修改
    * 缺点：比较复杂，混乱，还需要回滚，时间复杂度高
    * */

//    List<int[]> buffer = new ArrayList<>();
//    public void solve(char[][] board) {
//        for(int i = 1; i < board.length-1; i++){
//            for(int j =1; j < board[i].length-1; j++){
//                if(board[i][j] == 'O' && !solve(board, i, j)){
//                    setBuffer(board);
//                }
//                buffer = new ArrayList<>();
//            }
//        }
//    }
//
//    public boolean solve(char[][] board, int x, int y){
//        if(x<0 || y<0 || x >= board.length || y >= board[x].length){
//            return false;
//        }
//
//        if(board[x][y]== 'X'){
//            return true;
//        }
//
//        if(x>1 && board[x-1][y] == 'O'){
//            return false;
//        }
//
//        board[x][y] = 'X';
//        buffer.add(new int[]{x, y});
//        return solve(board, x-1, y) && solve(board, x, y+1) && solve(board, x+1, y) && solve(board, x, y-1) ;
//    }
//
//    private void setBuffer(char[][] board){
//        for (int[] ints : buffer){
//            board[ints[0]][ints[1]] = 'O';
//        }
//    }


}
